package hot100.logos1To10;

/**
 * @author logos
 * date 2025/7/9 19:58
 * @version v1.0
 * @Package hot100
 */
public class logos7 {

    /**
     * 7.接雨水
     * https://leetcode.cn/problems/trapping-rain-water/solutions/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution1 {
        public int trap(int[] height) {
            int n = height.length;
            int l = 1;
            int r = n - 2;
            int lmax = height[0];
            int rmax = height[n - 1];
            int ans = 0;
            while (l <= r) {
                if (lmax < rmax) {
                    ans += Math.max(0, lmax - height[l]);
                    lmax = Math.max(lmax, height[l]);
                    l++;
                } else {
                    ans += Math.max(0, rmax - height[r]);
                    rmax = Math.max(rmax, height[r]);
                    r--;
                }
            }
            return ans;
        }
    }

    class Solution2 {
        public int trap(int[] height) {
            int n = height.length;
            int[] lmax = new int[n];
            lmax[0] = height[0];
            for (int i = 1; i < n; i++) {
                lmax[i] = Math.max(height[i], lmax[i - 1]);
            }
            int[] rmax = new int[n];
            rmax[n - 1] = height[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                rmax[i] = Math.max(height[i], rmax[i + 1]);
            }
            int ans = 0;
            for (int i = 1; i < n - 1; i++) {
                ans += Math.max(0, Math.min(lmax[i - 1], rmax[i + 1]) - height[i]);
            }
            return ans;
        }
    }
}
